package cs561.hao;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.Vector;

public class Alpha_beta_pruning// show leaf node, succeed!
//try to show 1st step.
//.. is the line I revised compared to abp_test.java
{
	
	public static int expand_num = 0;

	public static void print_utility(TreeNode _node)
	{
		System.out.println(_node.utility + " ");
	}
	
	public static void DFS(TreeNode _node) 
	{
		if (_node.leaf == true)
		{
			//print_utility(_node);
			System.out.println("Leaf node!");
		}
		else
		{
			for(int i = 0; i < _node.childrenList.size(); i++)
			{
				//System.out.println("ChildrenList.size() = " + _node.childrenList.size());
				System.out.print(_node.nodeName + ": ");
				print_utility(_node);
				
				System.out.print(_node.childrenList.get(i).nodeName + ": ");
				print_utility(_node.childrenList.get(i));
				DFS(_node.childrenList.get(i));
			}		
			
/*			for(int i = 0; i < _node.childrenList.size(); i++)
			{
				print_utility(_node.childrenList.get(i));
			}*/
		}
	}
	
/*	class PlayerInfo
	{// player's info. of the map
		int x_current;
		int y_current;
		int i_last;
		int j_last;		
	}*/
			
	public static TreeNode caculateMinDistance(TreeNode _node, ArrayList<int[]> _finishCells)
	{
		//p1
		int[] tempFinishCell = _finishCells.get(0);
		double distance;
		double minDistance_p1 = Double.MAX_VALUE;		
		for(int i = 0; i < _finishCells.size(); i++)
		{
			tempFinishCell = _finishCells.get(i);//_finishCells.get(i).[0] x coordinate
			distance = Math.sqrt(Math.pow((_node.p1.x_current - tempFinishCell[0]),2) + Math.pow((_node.p1.y_current - tempFinishCell[1]),2));
			if((i == 0) || (distance < minDistance_p1))
			{
				minDistance_p1 = distance;
			}
		}
		_node.p1.minDistance = minDistance_p1;
		//p2
		double minDistance_p2 = Double.MAX_VALUE;		
		for(int i = 0; i < _finishCells.size(); i++)
		{
			tempFinishCell = _finishCells.get(i);//_finishCells.get(i).[0] x coordinate
			distance = Math.sqrt(Math.pow((_node.p2.x_current - tempFinishCell[0]),2) + Math.pow((_node.p2.y_current - tempFinishCell[1]),2));
			if((i == 0) || (distance < minDistance_p2))
			{
				minDistance_p2 = distance;
			}
		}
		_node.p2.minDistance = minDistance_p2;
		
		return _node;		
	}

	public static int evaluation(TreeNode _node, ArrayList<int[]> _finishCells, int _func_type)//if player1's turn, then isPlayer1Max is true
	{

		int expect_utility;
		
		int[] tempFinishCell = _finishCells.get(0);
		double distance;
		double minDistance_p1 = Double.MAX_VALUE;		
		for(int i = 0; i < _finishCells.size(); i++)
		{
			tempFinishCell = _finishCells.get(i);//_finishCells.get(i).[0] x coordinate
			distance = Math.sqrt(Math.pow((_node.p1.x_current - tempFinishCell[0]),2) + Math.pow((_node.p1.y_current - tempFinishCell[1]),2));
			if((i == 0) || (distance < minDistance_p1))
			{
				minDistance_p1 = distance;
			}
		}		
		_node.p1.minDistance = minDistance_p1;
		
		double minDistance_p2 = Double.MAX_VALUE;
		for(int i = 0; i < _finishCells.size(); i++)
		{
			tempFinishCell = _finishCells.get(i);//_finishCells.get(i).[0] x coordinate
			distance = Math.sqrt(Math.pow((_node.p2.x_current - tempFinishCell[0]),2) + Math.pow((_node.p2.y_current - tempFinishCell[1]),2));
			if((i == 0) || (distance < minDistance_p2))
			{
				minDistance_p2 = distance;
			}
		}
		
		_node.p2.minDistance = minDistance_p2;
		
		int steps_p1;
		int steps_p2;
		double speed_p1 = Math.sqrt(Math.pow(_node.p1.i_last, 2) + Math.pow(_node.p1.j_last, 2));
		//System.out.println("speed_p1 = " + speed_p1);
		double speed_p2 = Math.sqrt(Math.pow(_node.p2.i_last, 2) + Math.pow(_node.p2.j_last, 2));
		//System.out.println("speed_p2 = " + speed_p2);	
		steps_p1 = (int) (minDistance_p1/speed_p1);
		//System.out.println("steps_p1 = " + steps_p1);
		steps_p2 = (int) (minDistance_p2/speed_p2);
		//System.out.println("steps_p2 = " + steps_p2);
				
		if(_func_type == 1)
		{
			expect_utility =  steps_p2 - steps_p1;
		}
		if(_func_type == 2)
		{
			expect_utility =  (int) (steps_p2 - steps_p1 + minDistance_p2 - minDistance_p1);
		}
		else
		{
			expect_utility =  (int) (steps_p2 - steps_p1 + minDistance_p2 * 2 - minDistance_p1 * 2);
		}

		
		//expect_utility =  steps_p2;		
		
		return expect_utility;
	}

	public static TreeNode getNewNode_p1(TreeNode _parentNode, int _vectorDiffNum, int[][] _originalCells, ArrayList<int[]> _finishCells, int _func_type_p1)
	{//? do i have to add full stop?
		//need to check x,y duplicated?
		//need to check TreeNode duplicated?
		
		ArrayList<int[]> vectorDiffList = new ArrayList<int[]>();
		int[] tempArray = new int[2];
		tempArray[0] = -1;
		tempArray[1] = -1;		
		vectorDiffList.add(tempArray);
		
		tempArray = new int[2];
		tempArray[0] = 0;
		tempArray[1] = -1;		
		vectorDiffList.add(tempArray);
		
		tempArray = new int[2];
		tempArray[0] = 1;
		tempArray[1] = -1;		
		vectorDiffList.add(tempArray);
		
		tempArray = new int[2];
		tempArray[0] = -1;
		tempArray[1] = 0;		
		vectorDiffList.add(tempArray);
		
		tempArray = new int[2];
		tempArray[0] = 0;
		tempArray[1] = 0;		
		vectorDiffList.add(tempArray);
		
		tempArray = new int[2];
		tempArray[0] = 1;
		tempArray[1] = 0;		
		vectorDiffList.add(tempArray);
		
		tempArray = new int[2];
		tempArray[0] = -1;
		tempArray[1] = 1;		
		vectorDiffList.add(tempArray);
		
		tempArray = new int[2];
		tempArray[0] = 0;
		tempArray[1] = 1;		
		vectorDiffList.add(tempArray);
		
		tempArray = new int[2];
		tempArray[0] = 1;
		tempArray[1] = 1;		
		vectorDiffList.add(tempArray);
		
		int maxSpeed = 30;
		//p1 move
		
		int p1_i_new;
		int p1_j_new;
		if(_vectorDiffNum == 9)
		{
			p1_i_new = 0;
			p1_j_new = 0;
		}
		else
		{
			p1_i_new = _parentNode.p1.i_last + vectorDiffList.get(_vectorDiffNum)[0];
			p1_j_new = _parentNode.p1.j_last + vectorDiffList.get(_vectorDiffNum)[1];
		}
		
		if(Math.abs(p1_i_new) > maxSpeed)
		{
			if(p1_i_new < 0) p1_i_new = -maxSpeed;
			else p1_i_new = maxSpeed;
		}
		
		if(Math.abs(p1_j_new) > maxSpeed)
		{
			if(p1_j_new < 0) p1_j_new = -maxSpeed;
			else p1_j_new = maxSpeed;
		}
		int p1_x_new = _parentNode.p1.x_current + p1_i_new;
		int p1_y_new = _parentNode.p1.y_current + p1_j_new;
		//p2 stay;
		
		// check off road
		Vector<int[]> breakDownVectors = GamePlaying.breakTheMovementVector(p1_i_new,p1_j_new);//! do I have to static break method in Game.java?
		Iterator it = breakDownVectors.iterator();
		boolean valid = true;
		int[] currentPlayerLocation = new int[]{_parentNode.p1.x_current,_parentNode.p1.y_current};
		while(it.hasNext())
		{
			int[] step = (int[])it.next();
			currentPlayerLocation[0] += step[0];
			currentPlayerLocation[1] += step[1];
			if(_originalCells[currentPlayerLocation[1]][currentPlayerLocation[0]] == -1)
			{
				valid = false;
				break;
			}
		}//end while
		
		//check hit opponent
		if((p1_x_new == _parentNode.p2.x_current) && (p1_y_new == _parentNode.p2.y_current))
		{
			valid = false;// hit opponent
		}
		
		TreeNode  newNode = new TreeNode();
		//copy parent's a b to current node
		newNode.alpha = _parentNode.alpha;
		newNode.beta = _parentNode.beta;
		//newNode.leaf = true;
		//p1 move
		newNode.p1.x_current = p1_x_new;
		newNode.p1.y_current = p1_y_new;
		newNode.p1.i_last = p1_i_new;
		newNode.p1.j_last = p1_j_new;
		//p2 stay
		newNode.p2.x_current = _parentNode.p2.x_current;
		newNode.p2.y_current = _parentNode.p2.y_current;
		newNode.p2.i_last = _parentNode.p2.i_last;
		newNode.p2.j_last = _parentNode.p2.j_last;
		
		newNode.utility = evaluation(newNode, _finishCells, _func_type_p1);
	
		newNode.valid = valid;
		
		return newNode;		
	}//end newNode_p1
	
	public static TreeNode getNewNode_p2(TreeNode _parentNode, int _vectorDiffNum, int[][] _originalCells, ArrayList<int[]> _finishCells, int _func_type_p2)
	{//? do i have to add full stop?
		//need to check x,y duplicated?
		//need to check TreeNode duplicated?
		
		ArrayList<int[]> vectorDiffList = new ArrayList<int[]>();
		int[] tempArray = new int[2];
		tempArray[0] = -1;
		tempArray[1] = -1;		
		vectorDiffList.add(tempArray);
		
		tempArray = new int[2];
		tempArray[0] = 0;
		tempArray[1] = -1;		
		vectorDiffList.add(tempArray);
		
		tempArray = new int[2];
		tempArray[0] = 1;
		tempArray[1] = -1;		
		vectorDiffList.add(tempArray);
		
		tempArray = new int[2];
		tempArray[0] = -1;
		tempArray[1] = 0;		
		vectorDiffList.add(tempArray);
		
		tempArray = new int[2];
		tempArray[0] = 0;
		tempArray[1] = 0;		
		vectorDiffList.add(tempArray);
		
		tempArray = new int[2];
		tempArray[0] = 1;
		tempArray[1] = 0;		
		vectorDiffList.add(tempArray);
		
		tempArray = new int[2];
		tempArray[0] = -1;
		tempArray[1] = 1;		
		vectorDiffList.add(tempArray);
		
		tempArray = new int[2];
		tempArray[0] = 0;
		tempArray[1] = 1;		
		vectorDiffList.add(tempArray);
		
		tempArray = new int[2];
		tempArray[0] = 1;
		tempArray[1] = 1;		
		vectorDiffList.add(tempArray);
		
		int maxSpeed = 30;
		//p2 move
		
		int p2_i_new;
		int p2_j_new;
		if(_vectorDiffNum == 9)
		{
			p2_i_new = 0;
			p2_j_new = 0;
		}
		else
		{
			p2_i_new = _parentNode.p2.i_last + vectorDiffList.get(_vectorDiffNum)[0];
			p2_j_new = _parentNode.p2.j_last + vectorDiffList.get(_vectorDiffNum)[1];
		}
		if(Math.abs(p2_i_new) > maxSpeed)
		{
			if(p2_i_new < 0) p2_i_new = -maxSpeed;
			else p2_i_new = maxSpeed;
		}
		
		if(Math.abs(p2_j_new) > maxSpeed)
		{
			if(p2_j_new < 0) p2_j_new = -maxSpeed;
			else p2_j_new = maxSpeed;
		}
		int p2_x_new = _parentNode.p2.x_current + p2_i_new;
		int p2_y_new = _parentNode.p2.y_current + p2_j_new;
		//p1 stay;
		
		// check off road
		Vector<int[]> breakDownVectors = GamePlaying.breakTheMovementVector(p2_i_new,p2_j_new);//! do I have to static break method in Game.java?
		Iterator it = breakDownVectors.iterator();
		boolean valid = true;
		int[] currentPlayerLocation = new int[]{_parentNode.p2.x_current,_parentNode.p2.y_current};
		while(it.hasNext())
		{
			int[] step = (int[])it.next();
			currentPlayerLocation[0] += step[0];
			currentPlayerLocation[1] += step[1];
			if(_originalCells[currentPlayerLocation[1]][currentPlayerLocation[0]] == -1)
			{
				valid = false;
				break;
			}
		}//end while
		
		//check hit opponent
		if((p2_x_new == _parentNode.p1.x_current) && (p2_y_new == _parentNode.p1.y_current))
		{
			valid = false;// hit opponent
		}
		
		TreeNode  newNode = new TreeNode();
		//copy parent's a b to current node
		newNode.alpha = _parentNode.alpha;
		newNode.beta = _parentNode.beta;
		//newNode.leaf = true;
		//p2 move
		newNode.p2.x_current = p2_x_new;
		newNode.p2.y_current = p2_y_new;
		newNode.p2.i_last = p2_i_new;
		newNode.p2.j_last = p2_j_new;
		//p1 stay
		newNode.p1.x_current = _parentNode.p1.x_current;
		newNode.p1.y_current = _parentNode.p1.y_current;
		newNode.p1.i_last = _parentNode.p1.i_last;
		newNode.p1.j_last = _parentNode.p1.j_last;
		
		newNode.utility = evaluation(newNode, _finishCells,_func_type_p2);
				
		newNode.valid = valid;
		
		return newNode;		
	}//end newNode_p2
	
	//public static TreeNode abp(TreeNode _node, int _depth, int _alpha, int _beta, int _player, int[][] _originalCells)//..
	public static TreeNode abp(TreeNode _node, int _depth, int _player, int[][] _originalCells, ArrayList<int[]> _finishCells, int _func_type_p1, int _func_type_p2)//..
	{// the return node is the best next move of _node.		
		if ((_depth == 0) || (_node.p1.minDistance == 0) || (_node.p2.minDistance == 0))//
		//if (_depth == 0)//
		{		
			if((_node.p1.minDistance == 0) || (_node.p2.minDistance == 0)) 
				System.out.println("!!!!!!!!!!!!!! This line will never print because when getNewNode, if dis == 0, won't go 1 level down!!!!!!!!!!!!!!!!!!!!");
			System.out.println("");
			System.out.println("\n << Return leaf node: " + _node.nodeName + ", depth = " + _depth);			
			
			System.out.println(_node.nodeName + ": rt = " + _node.root + ", lf = " + _node.leaf + ", uti = " 
					+ _node.utility + ", pa = " + _node.parent.nodeName + ", a = " + _node.alpha + ", b = " + _node.beta + ", uti = " + _node.utility);
			
			System.out.println(_node.nodeName + ".p1: (x,y,i_last,j_last,minD,uti) = (" + _node.p1.x_current + "," 
					+ _node.p1.y_current + "," + _node.p1.i_last + "," + _node.p1.j_last + "," + _node.p1.minDistance + "," + _node.utility + ")");
			
			System.out.println(_node.nodeName + ".p2: (x,y,i_last,j_last,minD,uti) = (" + _node.p2.x_current + "," 
					+ _node.p2.y_current + "," + _node.p2.i_last + "," + _node.p2.j_last + "," + _node.p2.minDistance + "," + _node.utility + ")");			
			
			System.out.println(" end return leaf node. >>");	

			return _node;//..
		}
		else if(_player == 1)//max
		{						
			TreeNode bestChoiceNode = _node;//.. here use reference is better than new a node.				
			_node = caculateMinDistance(_node, _finishCells);
			_depth--;
			
			for(int i = 0; i < 10; i++)
			{
				System.out.println("\n Parent node: " + _node.nodeName + ": rt = " + _node.root + ", lf = " + _node.leaf + ", uti = " 
						+ _node.utility + ", pa = " + _node.parent.nodeName + ", a = " + _node.alpha + ", b = " + _node.beta + ", uti = " + _node.utility + ", best node = " + bestChoiceNode.nodeName);
				
				System.out.println(_node.nodeName + ".p1: (x,y,i_last,j_last,minD,uti) = (" + _node.p1.x_current + "," 
						+ _node.p1.y_current + "," + _node.p1.i_last + "," + _node.p1.j_last + "," + _node.p1.minDistance + "," + _node.utility + ")");
				
				System.out.println(_node.nodeName + ".p2: (x,y,i_last,j_last,minD,uti) = (" + _node.p2.x_current + "," 
						+ _node.p2.y_current + "," + _node.p2.i_last + "," + _node.p2.j_last + "," + _node.p2.minDistance + "," + _node.utility + ")");
				
				//create a new node, p1 move, p2 stay, but not add to game tree yet
				TreeNode max_p1_move_node = getNewNode_p1(_node, i, _originalCells, _finishCells, _func_type_p1);//p1 is always max, move p1
				
				if(max_p1_move_node == null)
				{
					System.out.println("abp: max_p1_move_node error !!!");
					System.exit(-1);
				}
				
				//caculate the p1/p2 minD				
				
				if(max_p1_move_node.valid == true)
				{
					max_p1_move_node.nodeName = "Node#" + expand_num++;
					max_p1_move_node = caculateMinDistance(max_p1_move_node, _finishCells);
					max_p1_move_node.utility = evaluation(max_p1_move_node,_finishCells, _func_type_p1); 
					_node.addChild(max_p1_move_node);//if valid node, add to parent in the game tree				
					
					System.out.println("\n<< New node: add " + max_p1_move_node.nodeName + " to " + _node.nodeName 
							+ ", now " + _node.nodeName + " has children: " + _node.childrenList.size()); 
					
					System.out.println(max_p1_move_node.nodeName + ".p1: (x,y,i_last,j_last,minD,uti) = (" + max_p1_move_node.p1.x_current + "," 
							+ max_p1_move_node.p1.y_current + "," + max_p1_move_node.p1.i_last + "," + 
							max_p1_move_node.p1.j_last + "," + max_p1_move_node.p1.minDistance + "," + max_p1_move_node.utility +")");
					
					System.out.println(max_p1_move_node.nodeName + ".p2: (x,y,i_last,j_last,minD,uti) = (" + max_p1_move_node.p2.x_current + "," 
							+ max_p1_move_node.p2.y_current + "," + max_p1_move_node.p2.i_last + "," + 
							max_p1_move_node.p2.j_last + "," + max_p1_move_node.p2.minDistance + "," +  max_p1_move_node.utility + ")");
					System.out.println(" end new node. >>");
					
					if(max_p1_move_node.p1.minDistance == 0) 
					{
						max_p1_move_node.utility = Integer.MAX_VALUE;
						bestChoiceNode = max_p1_move_node;
						System.out.println("\n @ @ @ p1 foresee the finish cell! Try but not sure to arrive there!");
						_node.alpha = Math.max(_node.alpha, bestChoiceNode.utility);//update the a//..
						break;
					}	
					
					//recursive key!
					TreeNode max_p2_move_node = abp(max_p1_move_node, _depth, -_player, _originalCells, _finishCells, _func_type_p1, _func_type_p2);

					if(max_p2_move_node == null)
					{
						System.out.println("abp: max_p2_move_node error !!!");
						System.exit(-2);
					}
					//?				
					//if((bestChoiceNode == null) || (max_p2_move_node.utility >= bestChoiceNode.utility))//MAX
					if((bestChoiceNode == null) || (max_p2_move_node.utility >= bestChoiceNode.alpha))//MAX
					{
						bestChoiceNode = max_p2_move_node;
						//System.out.println("\nUpdate best choice: " + bestChoiceNode.nodeName);
						//max_p1_move_node.utility = bestChoiceNode.utility;
						
					}
					//,
//					System.out.println(" & & Children's : (best node, best uti) = (" + max_p2_move_node.nodeName + "," + max_p2_move_node.utility + ")");
//					System.out.println(" & &    Current : (best node, best uti) = (" + bestChoiceNode.nodeName + "," + bestChoiceNode.utility + ")");
//					System.out.print("\nUpdate alpha: (node, old alpha, new alpha, best, best.uti) = (" + _node.nodeName + "," + _node.alpha);					
					_node.alpha = Math.max(_node.alpha, bestChoiceNode.utility);//update the a//..
//					System.out.println("," + _node.alpha  + "," + bestChoiceNode.nodeName + "," + bestChoiceNode.utility + ")\n");
					
					if (_node.alpha >= _node.beta)
					{
						System.out.println("\n X X X \n   " + _node.nodeName + " pruned.\n X X X");
						//_node.alpha = Integer.MAX_VALUE;//?
						//_node.alpha = 99;
						System.out.println();
						break;
					}
				}//end valid true				
								
			}//end for
			_node.utility = bestChoiceNode.utility;
			System.out.println("<<No more valid nodes. Max Return node: " + _node.nodeName + ".(a,b,clist,uti,bestNode) = (" + _node.alpha + "," + _node.beta + "," 
					+ _node.childrenList.size() + "," + _node.utility + ", " + bestChoiceNode.nodeName + ") >>");
			
			return bestChoiceNode;
		}
		else//MIN
		{			
			TreeNode bestChoiceNode = _node;
			_node = caculateMinDistance(_node, _finishCells);
			_depth--;			
				
			for(int i = 0; i < 10; i++)
			{
				System.out.println("\n Parent node: "+ _node.nodeName + ": rt = " + _node.root + ", lf = " + _node.leaf + ", uti = " 
						+ _node.utility + ", pa = " + _node.parent.nodeName + ", a = " + _node.alpha + ", b = " + _node.beta + ", uti = " + _node.utility + ", best node = " + bestChoiceNode.nodeName);
				
				System.out.println(_node.nodeName + ".p1: (x,y,i_last,j_last,minD,uti) = (" + _node.p1.x_current + "," 
						+ _node.p1.y_current + "," + _node.p1.i_last + "," + _node.p1.j_last + "," + _node.p1.minDistance + "," + _node.utility + ")");
				
				System.out.println(_node.nodeName + ".p2: (x,y,i_last,j_last,minD,uti) = (" + _node.p2.x_current + "," 
						+ _node.p2.y_current + "," + _node.p2.i_last + "," + _node.p2.j_last + "," + _node.p2.minDistance + "," + _node.utility + ")");			
				
				//create a new node, p2 move, p1 stay, but not add to game tree yet
				TreeNode min_p2_move_node = getNewNode_p2(_node, i, _originalCells, _finishCells,_func_type_p2);

				if(min_p2_move_node == null)
				{
					System.out.println("abp: min_p2_move_node error !!!");
					System.exit(-3);
				}
				
				//caculate the p1/p2 minD	
								
				if(min_p2_move_node.valid == true)
				{
					min_p2_move_node.nodeName = "Node#" + expand_num++;
					min_p2_move_node = caculateMinDistance(min_p2_move_node, _finishCells);
					min_p2_move_node.utility = evaluation(min_p2_move_node,_finishCells,_func_type_p2); 
					_node.addChild(min_p2_move_node);//if valid node, add to parent
					
					System.out.println("\n<< New node: add " + min_p2_move_node.nodeName + " to " + _node.nodeName 
							+ ", now " + _node.nodeName + " has children: " + _node.childrenList.size()); 
					
					System.out.println(min_p2_move_node.nodeName + ".p1: (x,y,i_last,j_last,minD,uti) = (" + min_p2_move_node.p1.x_current + "," 
							+ min_p2_move_node.p1.y_current + "," + min_p2_move_node.p1.i_last + "," + 
							min_p2_move_node.p1.j_last + "," + min_p2_move_node.p1.minDistance + "," + min_p2_move_node.utility + ")");
					
					System.out.println(min_p2_move_node.nodeName + ".p2: (x,y,i_last,j_last,minD,uti) = (" + min_p2_move_node.p2.x_current + "," 
							+ min_p2_move_node.p2.y_current + "," + min_p2_move_node.p2.i_last + "," + 
							min_p2_move_node.p2.j_last + "," + min_p2_move_node.p2.minDistance + "," + min_p2_move_node.utility + ")");								
					System.out.println(" end new node. >>");
					
					if(min_p2_move_node.p2.minDistance == 0)
					{
						min_p2_move_node.utility = Integer.MIN_VALUE;
						bestChoiceNode = min_p2_move_node;
						System.out.println("\n @ @ @ p2 foresee the finish cell! Try but not sure to arrive there!");

						_node.beta = Math.min(_node.beta, bestChoiceNode.utility);
						break;
					}					
					
					//recursive key!
					TreeNode min_p1_move_node = abp(min_p2_move_node, _depth, -_player, _originalCells, _finishCells,_func_type_p1,_func_type_p2);
					
					if(min_p1_move_node == null)
					{
						System.out.println("abp: min_p1_move_node error !!!");
						System.exit(-4);
					}
					//?
					//if((bestChoiceNode == null) || (min_p1_move_node.utility <= bestChoiceNode.utility))//MIN
					if((bestChoiceNode == null) || (min_p1_move_node.utility <= bestChoiceNode.beta))//MIN
					{
						bestChoiceNode = min_p1_move_node;
						//System.out.println("\nUpdate best choice: " + bestChoiceNode.nodeName);
						//min_p2_move_node.utility = bestChoiceNode.utility;
						
					}
					//,	
//					System.out.println(" & & Children's : (best node, best uti) = (" + min_p1_move_node.nodeName + "," + min_p1_move_node.utility + ")");
//					System.out.println(" & &    Current : (best node, best uti) = (" + bestChoiceNode.nodeName + "," + bestChoiceNode.utility + ")");
//					System.out.print("\nUpdate beta: (node, old beta, new beta, best, best.uti) = (" + _node.nodeName + "," + _node.beta);
					_node.beta = Math.min(_node.beta, bestChoiceNode.utility);//update the b//..
//					System.out.println("," + _node.beta + "," + bestChoiceNode.nodeName + "," + bestChoiceNode.utility + ")\n");
					
					if (_node.alpha >= _node.beta)
					{
						System.out.println("\n X X X \n   " + _node.nodeName + " pruned.\n X X X");
						//_node.alpha = Integer.MAX_VALUE;//?
						//_node.alpha = 99;
						System.out.println();
						break;
					}
				}//end valid true				
				
			}//end for
			_node.utility = bestChoiceNode.utility;
			System.out.println("<<No more valid nodes. Min Return node: " + _node.nodeName + ".(a,b,clist,uti,bestNode) = (" + _node.alpha + "," + _node.beta + "," 
					 + _node.childrenList.size() + "," + _node.utility + ", " + bestChoiceNode.nodeName + ") >>");				
			
			return bestChoiceNode;
		}		
	}//end abp
/*	
	public static void main(String[] args)
	{
		
		//construct treeA
		TreeNode_test node_a = new TreeNode_test();
		node_a.root = true;
		node_a.nodeName = "node_a";
		node_a.utility = 1;
		
		TreeNode_test node_b = new TreeNode_test();
		node_b.utility = 2;
		node_b.nodeName = "node_b";
		
		TreeNode_test node_c = new TreeNode_test();
		node_c.utility = 3;
		node_c.nodeName = "node_c";
		
		TreeNode_test node_d = new TreeNode_test();
		node_d.utility = 4;
		node_d.nodeName = "node_d";
		
		TreeNode_test node_e = new TreeNode_test();
		node_e.utility = 5;
		node_e.nodeName = "node_e";
		
		TreeNode_test node_f = new TreeNode_test();
		node_f.utility = 6;
		node_f.nodeName = "node_f";
		
		TreeNode_test node_g = new TreeNode_test();
		node_g.utility = 7;
		node_g.nodeName = "node_g";
		
		TreeNode_test node_h = new TreeNode_test();
		node_h.utility = 8;
		node_h.nodeName = "node_h";
		
		//depth 0.
		node_a.addChild(node_b);
		node_a.addChild(node_c);
		node_a.addChild(node_d);
		
		//depth 1.
		node_b.addChild(node_e);
		node_b.addChild(node_f);
		
		node_c.addChild(node_g);
		
		node_d.addChild(node_h);
		
		//print_utility(node_a);
		//print_utility(node_g);
		
		TreeNode_test result = abp(node_a, 5, Integer.MIN_VALUE, Integer.MAX_VALUE, 1);
		System.out.println("Max: " + result.utility);
		System.out.println("Best node name: " + result.nodeName);
		
		//end of treeA
		
		
		
		 //construct treeB
		TreeNode_test node_a = new TreeNode_test();
		node_a.root = true;
		node_a.nodeName = "node_a";
		node_a.utility = 1;
		
		TreeNode_test node_b = new TreeNode_test();
		node_b.utility = 2;
		node_b.nodeName = "node_b";
		
		TreeNode_test node_c = new TreeNode_test();
		node_c.utility = 3;
		node_c.nodeName = "node_c";
		
		TreeNode_test node_d = new TreeNode_test();
		node_d.utility = 4;
		node_d.nodeName = "node_d";
		
		TreeNode_test node_e = new TreeNode_test();
		node_e.utility = 5;
		node_e.nodeName = "node_e";//
		
		TreeNode_test node_f = new TreeNode_test();
		node_f.utility = 6;
		node_f.nodeName = "node_f";
		
		TreeNode_test node_g = new TreeNode_test();
		node_g.utility = 7;
		node_g.nodeName = "node_g";
		
		TreeNode_test node_h = new TreeNode_test();
		node_h.utility = 8;
		node_h.nodeName = "node_h";//
		
		TreeNode_test node_i = new TreeNode_test();
		node_i.utility = 9;
		node_i.nodeName = "node_i";//
		
		TreeNode_test node_j = new TreeNode_test();
		node_j.utility = 10;
		node_j.nodeName = "node_j";//
		//depth 0
		node_a.addChild(node_b);
		node_a.addChild(node_c);
		
		//depth 1
		node_b.addChild(node_d);
		node_b.addChild(node_e);
		
		node_c.addChild(node_f);
		
		//depth 2
		node_d.addChild(node_g);
		
		node_f.addChild(node_h);
		
		//depth 3
		node_g.addChild(node_i);
		node_g.addChild(node_j);
		
		//System.out.println(node_a.nodeName);
		//DFS(node_a);
		//DFS(node_b);
		//DFS(node_c);
		//DFS(node_d);
		//DFS(node_e);
		
		TreeNode_test result = abp(node_a, 4, Integer.MIN_VALUE, Integer.MAX_VALUE, 1);
		System.out.println("Max: " + result.utility);
		System.out.println("Best node name: " + result.nodeName);
		 //end of treeB
		
		 //construct treeC
		TreeNode node_a = new TreeNode();
		node_a.root = true;
		node_a.nodeName = "node_a";
		node_a.utility = 2;
		
		TreeNode node_b = new TreeNode();
		node_b.utility = 3;
		node_b.nodeName = "node_b";
		
		TreeNode node_c = new TreeNode();
		node_c.utility = 1;
		node_c.nodeName = "node_c";
		
		TreeNode node_d = new TreeNode();
		node_d.utility = 3;
		node_d.nodeName = "node_d";
		
		TreeNode node_e = new TreeNode();
		node_e.utility = 2;
		node_e.nodeName = "node_e";//
		
		TreeNode node_f = new TreeNode();
		node_f.utility = 5;
		node_f.nodeName = "node_f";
		
		TreeNode node_g = new TreeNode();
		node_g.utility = 8;
		node_g.nodeName = "node_g";
		
		TreeNode node_h = new TreeNode();
		node_h.utility = 7;
		node_h.nodeName = "node_h";//
		
		TreeNode node_i = new TreeNode();
		node_i.utility = 10;
		node_i.nodeName = "node_i";//
		
		TreeNode node_j = new TreeNode();
		node_j.utility = 9;
		node_j.nodeName = "node_j";//
		//depth 0
		node_a.addChild(node_b);
		node_a.addChild(node_c);
		
		//depth 1
		node_b.addChild(node_d);
		node_b.addChild(node_e);
		
		node_c.addChild(node_f);
		
		//depth 2
		node_d.addChild(node_g);
		
		node_f.addChild(node_h);
		
		//depth 3
		node_g.addChild(node_i);
		node_g.addChild(node_j);
		
		//System.out.println(node_a.nodeName);
		//DFS(node_a);
		//DFS(node_b);
		//DFS(node_c);
		//DFS(node_d);
		//DFS(node_e);
		
		TreeNode result = abp(node_a, 1, Integer.MIN_VALUE, Integer.MAX_VALUE, 1);
		System.out.println("Max: " + result.utility);
		System.out.println("Best node name: " + result.nodeName);
		 //end of treeC		
		
		
		
		//build treeD
		TreeNode_test node_01 = new TreeNode_test();
		node_01.root = true;
		node_01.nodeName = "node_01";
		//node_01.utility = 0;
		
		TreeNode_test node_02 = new TreeNode_test();
		node_02.nodeName = "node_02";
		//node_02.utility = 0;
		
		TreeNode_test node_03 = new TreeNode_test();
		node_03.nodeName = "node_03";
		//node_03.utility = 0;
		
		TreeNode_test node_04 = new TreeNode_test();
		node_04.nodeName = "node_04";
		//node_04.utility = 0;
		
		TreeNode_test node_05 = new TreeNode_test();
		node_05.nodeName = "node_05";
		//node_05.utility = 0;
		
		TreeNode_test node_06 = new TreeNode_test();
		node_06.nodeName = "node_06";
		//node_06.utility = 0;
		
		TreeNode_test node_07 = new TreeNode_test();
		node_07.nodeName = "node_07";
		node_07.utility = 3;
		
		TreeNode_test node_08 = new TreeNode_test();
		node_08.nodeName = "node_08";
		//node_08.utility = 0;
		
		TreeNode_test node_09 = new TreeNode_test();
		node_09.nodeName = "node_09";
		//node_09.utility = 0;
		
		TreeNode_test node_10 = new TreeNode_test();
		node_10.nodeName = "node_10";
		//node_10.utility = 0;
		
		TreeNode_test node_11 = new TreeNode_test();
		node_11.nodeName = "node_11";
		//node_11.utility = 0;
		
		TreeNode_test node_12 = new TreeNode_test();
		node_12.nodeName = "node_12";
		//node_12.utility = 0;
		
		TreeNode_test node_13 = new TreeNode_test();
		node_13.nodeName = "node_13";
		//node_13.utility = 0;
		
		TreeNode_test node_14 = new TreeNode_test();
		node_14.nodeName = "node_14";
		//node_14.utility = 0;
		
		TreeNode_test node_15 = new TreeNode_test();
		node_15.nodeName = "node_15";
		//node_15.utility = 0;
		
		TreeNode_test node_16 = new TreeNode_test();
		node_16.nodeName = "node_16";
		//node_16.utility = 0;
		
		TreeNode_test node_17 = new TreeNode_test();
		node_17.nodeName = "node_17";
		node_17.utility = 7;
		
		TreeNode_test node_18 = new TreeNode_test();
		node_18.nodeName = "node_18";
		//node_18.utility = 0;
		
		TreeNode_test node_19 = new TreeNode_test();
		node_19.nodeName = "node_19";
		//node_19.utility = 0;
		
		TreeNode_test node_20 = new TreeNode_test();
		node_20.nodeName = "node_20";
		//node_20.utility = 0;
		
		TreeNode_test node_21 = new TreeNode_test();
		node_21.nodeName = "node_21";
		//node_21.utility = 0;
		
		TreeNode_test node_22 = new TreeNode_test();
		node_22.nodeName = "node_22";
		node_22.utility = 10;
		
		TreeNode_test node_23 = new TreeNode_test();
		node_23.nodeName = "node_23";
		node_23.utility = 15;
		
		TreeNode_test node_24 = new TreeNode_test();
		node_24.nodeName = "node_24";
		node_24.utility = 13;
		
		TreeNode_test node_25 = new TreeNode_test();
		node_25.nodeName = "node_25";
		node_25.utility = 7;
		
		TreeNode_test node_26 = new TreeNode_test();
		node_26.nodeName = "node_26";
		node_26.utility = 100;
		
		TreeNode_test node_27 = new TreeNode_test();
		node_27.nodeName = "node_27";
		node_27.utility = 20;
		
		TreeNode_test node_28 = new TreeNode_test();
		node_28.nodeName = "node_28";
		node_28.utility = 11;
		
		TreeNode_test node_29 = new TreeNode_test();
		node_29.nodeName = "node_29";
		node_29.utility = 5;
		
		TreeNode_test node_30 = new TreeNode_test();
		node_30.nodeName = "node_30";
		node_30.utility = 4;
		
		TreeNode_test node_31 = new TreeNode_test();
		node_31.nodeName = "node_31";
		node_31.utility = 70;
		
		TreeNode_test node_32 = new TreeNode_test();
		node_32.nodeName = "node_32";
		node_32.utility = 6;
		
		TreeNode_test node_33 = new TreeNode_test();
		node_33.nodeName = "node_33";
		node_33.utility = 2;
		
		TreeNode_test node_34 = new TreeNode_test();
		node_34.nodeName = "node_34";
		node_34.utility = 17;
		
		TreeNode_test node_35 = new TreeNode_test();
		node_35.nodeName = "node_35";
		node_35.utility = 1;
		
		TreeNode_test node_36 = new TreeNode_test();
		node_36.nodeName = "node_36";
		node_36.utility = 20;
		
		TreeNode_test node_37 = new TreeNode_test();
		node_37.nodeName = "node_37";
		node_37.utility = 50;
		
		//depth 0
		node_01.addChild(node_02);
		node_01.addChild(node_03);
		node_01.addChild(node_04);
		
		//depth 1
		node_02.addChild(node_05);
		node_02.addChild(node_06);
		node_02.addChild(node_07);
		
		node_03.addChild(node_08);
		node_03.addChild(node_09);
		
		node_04.addChild(node_10);
		node_04.addChild(node_11);
		
		//depth 2
		node_05.addChild(node_12);
		node_05.addChild(node_13);
		node_05.addChild(node_14);
		
		node_06.addChild(node_15);
		node_06.addChild(node_16);
		
		node_08.addChild(node_17);
		node_08.addChild(node_18);
		
		node_09.addChild(node_19);
		
		node_10.addChild(node_20);
		
		node_11.addChild(node_21);
		
		//depth 3
		node_12.addChild(node_22);
		node_12.addChild(node_23);
		node_12.addChild(node_24);
		
		node_13.addChild(node_25);
		node_13.addChild(node_26);
		
		node_14.addChild(node_27);
		
		node_15.addChild(node_28);
		node_15.addChild(node_29);
		
		node_16.addChild(node_30);
		node_16.addChild(node_31);
		
		node_18.addChild(node_32);
		
		node_19.addChild(node_33);
		node_19.addChild(node_34);
		
		node_20.addChild(node_35);
		node_20.addChild(node_36);
		
		node_21.addChild(node_37);
		
		//DFS(node_01);// test, succeed!
		TreeNode_test result = abp(node_01, 2, Integer.MIN_VALUE, Integer.MAX_VALUE, 1);
		//int result = abp(node_12, 1, Integer.MIN_VALUE, Integer.MAX_VALUE, -1);
		System.out.println("MAX: " + result.utility);
		System.out.println("Best bottom node name: " + result.nodeName);
		
		 //end of treeD;
	
		
		
			 
		//build treeE
		TreeNode_test node_01 = new TreeNode_test();
		node_01.root = true;
		node_01.nodeName = "node_01";
		//node_01.alpha = Integer.MIN_VALUE;
		//node_01.beta = Integer.MAX_VALUE;
		
		TreeNode_test node_02 = new TreeNode_test();
		node_02.nodeName = "node_02";
		
		TreeNode_test node_03 = new TreeNode_test();
		node_03.nodeName = "node_03";
		
		TreeNode_test node_04 = new TreeNode_test();
		node_04.nodeName = "node_04";
		node_04.utility = 7;
		
		TreeNode_test node_05 = new TreeNode_test();
		node_05.nodeName = "node_05";
		node_05.utility = 6;
		
		TreeNode_test node_06 = new TreeNode_test();
		node_06.nodeName = "node_06";
		node_06.utility = 5;
		
		TreeNode_test node_07 = new TreeNode_test();
		node_07.nodeName = "node_07";
		node_07.utility = 4;
		
		TreeNode_test node_08 = new TreeNode_test();
		node_08.nodeName = "node_08";
		node_08.utility = 9;
		
		//depth 0;
		node_01.addChild(node_02);
		node_01.addChild(node_03);
		node_01.addChild(node_08);
		
		//depth 1;
		node_02.addChild(node_04);
		node_02.addChild(node_05);
		
		node_03.addChild(node_06);
		node_03.addChild(node_07);
		
		//DFS(node_01);
		TreeNode_test result = abp(node_01, 2, Integer.MIN_VALUE, Integer.MAX_VALUE, 1);
		System.out.println("Max: " + result.utility);
		System.out.println("Best node name: " + result.nodeName);
		 //end of treeE
		
		
			
		
	}// end main	
	
*/	
}
